using System;
using UnityEngine;
using System.Collections;

public class SAPathFinder
{

	public const byte BLOCK1 = 2;
	public const byte BLOCK2 = 6;

	public const byte MAXBUFF = 128;

	
	class PathNode
	{
		public int posX = 0;
		public int posY = 0;

		public int f = 0;
		public int g = 0;
		public int n = 0;
		
		public PathNode parent = null;
		
		public void	clear()
		{
			parent = null;

			f = 0;
			g = 0;
			n = 0;
		}
		
		public PathNode()
		{

		}
	};

	
	public bool fly = false;

	
	private PathNode resultNode = null;
	private PathNode topNode = null;

	private PathNode[] openResult = null;
	private PathNode[] open = null;

	private byte[] close;

	private byte[] mapData = null;
	
	private int maxX = 0;
	private int maxY = 0;

	private int step = 0;

	private int openCount;
	private int openResultCount;


	private int startPosX;
	private int startPosY;
	private int endPosX;
	private int endPosY;


	private PathNode[] nodes;

	public SAPathFinder ()
	{

	}

	public void initMap( int x , int y , byte[] d )
	{
		maxX = x;
		maxY = y;

		mapData = d;

		close = new byte[ x * y ];

		open = new PathNode[ x * y ];
		openResult = new PathNode[ x * y ];

		nodes = new PathNode[ x * y ];
		for ( int i = 0; i < x * y ; i++ )
		{
			nodes[ i ] = new PathNode();
		}

		int count = 0;
		for ( int i = 0 ; i < y ; i++ )
		{
			for ( int j = 0 ; j < x ; j++ )
			{
				nodes[ count ].posX = j;
				nodes[ count ].posY = i;
				
				count++;
			}
		}
	}

	public bool isBlock( byte c )
	{
		if ( fly )
		{
			return false;
		}

		return c == BLOCK1;
	}

	public bool isBlock( int x , int y )
	{
		return isBlock( mapData[ getIndex( x , y ) ] );
	}


	public byte getMapData( int x , int y )
	{
		return mapData[ getIndex( x , y ) ];
	}

	public void setBlock( int x , int y , bool b )
	{
		mapData[ getIndex( x , y ) ] = b ? BLOCK1 : (byte)0;
	}

	public void setStartEnd( int sx , int sy , int ex , int ey )
	{
		startPosX = sx;
		startPosY = sy;

		endPosX = ex;
		endPosY = ey;
	}
	
	void findPath()
	{
		resultNode = null;

		if ( startPosX == endPosX && startPosY == endPosY )
		{
			return;
		}
		
		if ( isBlock( mapData[ getIndex( endPosX , endPosY ) ] ) )
		{
			return;
		}

		clear();
		
		open[ openCount ] = nodes[ getIndex( startPosX , startPosY ) ];
		open[ openCount ].g = 0;
		open[ openCount ].f = 0;
		open[ openCount ].parent = null;
		open[ openCount ].n = 0;
		
		openCount++;

		close[ getIndex( startPosX , startPosY ) ] = 1;
		topNode = open[ 0 ];
		topNode.clear();
		
		step = 1;
		int count = 0;

		while ( true )
		{
			count++;
			PathNode[] v1 = open;
			PathNode[] v2 = openResult;
			int c = openCount;


			if ( step > 0 )
			{
				step = 0;
			}
			else
			{
				v1 = openResult;
				v2 = open;
				
				step = 1;
				
				c = openResultCount;
			}
			
			for ( int i = 0 ; i < c ; ++i )
			{
				int n = find( v2 , v1[i] );
				
				if ( n > 0 )
				{
					return;
				}
			}
			
			
			if ( step > 0 )
			{
				openResultCount = 0;
				
				if ( openCount == 0 )
				{
					return;
				}
			}
			else
			{
				openCount = 0;
				
				if ( openResultCount == 0 )
				{
					return;
				}
			}

			
			if ( count == 1000 )
			{
				resultNode = null;
				return;
			}
			
			//        if ( step )
			//        {
			//            qsort( v2 , mOpenCount, sizeof( PathNode* ) , PathNodeLess );
			//        }
			//        else
			//        {
			//            qsort( v2 , mOpenResultCount, sizeof( PathNode* ) , PathNodeLess );
			//        }
			
			
			//qsort( v2  , v2->size() , sizeof( PathNode* ) , PathNodeLess );
		}
	}

	int	find( PathNode[] v , PathNode parent )
	{
		// s
		int posX = parent.posX;
		int posY = parent.posY;

		++posY;
		int find1 = find( v , parent , posX , posY , 10 );
		if ( find1 > 0 )
			return find1;
		
		// n
		posX = parent.posX;
		posY = parent.posY;
		--posY;
		find1 = find( v , parent , posX , posY , 10 );
		if ( find1 > 0 )
			return find1;

		// w
		posX = parent.posX;
		posY = parent.posY;
		--posX;
		find1 = find( v , parent , posX , posY , 10 );
		if ( find1 > 0 )
			return find1;
		
		// e
		posX = parent.posX;
		posY = parent.posY;
		++posX;
		find1 = find( v , parent , posX , posY , 10 );
		if ( find1 > 0 )
			return find1;
		

		// nw
		posX = parent.posX;
		posY = parent.posY;
		--posX;
		--posY;
		find1 = find( v , parent , posX , posY , 14 , 1 );
		if ( find1 > 0 )
			return find1;
		
		// ne
		posX = parent.posX;
		posY = parent.posY;
		++posX;
		--posY;
		find1 = find( v , parent , posX , posY , 14 , 2 );
		if ( find1 > 0 )
			return find1;
		
		// sw
		posX = parent.posX;
		posY = parent.posY;
		--posX;
		++posY;
		find1 = find( v , parent , posX , posY , 14 , 3 );
		if ( find1 > 0 )
			return find1;
		
		// se
		posX = parent.posX;
		posY = parent.posY;
		++posX;
		++posY;
		find1 = find( v , parent , posX , posY , 14 , 4 );
		if ( find1 > 0 )
			return find1;

		return 0;
	}


	int find( PathNode[] v , PathNode parent , int posX , int posY , int f , int n = 0 )
	{
		int index = getIndex( posX , posY );
		if ( index != GameDefine.INVALID_ID )
		{
			if ( close[ index ] != 1 )
			{
				if ( !isBlock( mapData[ index ] ) )
				{
					switch ( n )
					{
					case 1:
					{
						int posX1 = posX + 1;
						int posY1 = posY + 1;

						int index1 = getIndex( posX1 , posY );
						int index2 = getIndex( posX , posY1 );
						
						if ( isBlock( mapData[ index1 ] ) && isBlock( mapData[ index2 ] ) )
						{
							//mClose[ index ] = 1;
							return 0;
						}
					}
						break;
					case 2:
					{
						int posX1 = posX - 1;
						int posY1 = posY + 1;

						int index1 = getIndex( posX1 , posY );
						int index2 = getIndex( posX , posY1 );
						
						if ( isBlock( mapData[ index1 ] ) && isBlock( mapData[ index2 ] ) )
						{
							//mClose[ index ] = 1;
							return 0;
						}
					}
						break;
					case 3:
					{
						int posX1 = posX + 1;
						int posY1 = posY - 1;

						int index1 = getIndex( posX1 , posY );
						int index2 = getIndex( posX , posY1 );
						
						if ( isBlock( mapData[ index1 ] ) && isBlock( mapData[ index2 ] ) )
						{
							//mClose[ index ] = 1;
							return 0;
						}
					}
						break;
					case 4:
					{
						int posX1 = posX - 1;
						int posY1 = posY - 1;
						
						int index1 = getIndex( posX1 , posY );
						int index2 = getIndex( posX , posY1 );
						
						if ( isBlock( mapData[ index1 ] ) && isBlock( mapData[ index2 ] ) )
						{
							//mClose[ index ] = 1;
							return 0;
						}
					}
						break;
					}
					
					nodes[ index ].n = parent.n + 1;
					nodes[ index ].f = f;
					nodes[ index ].g = parent.g + f;
					nodes[ index ].parent = parent;

					
					if ( step != 0 )
					{
						v[ openCount ] = nodes[ index ];
						openCount++;
					}
					else
					{
						v[ openResultCount ] = nodes[ index ];
						openResultCount++;
					}
					//v->push_back( mNodes + index );
					
					if ( posX == endPosX && posY == endPosY )
					{
						resultNode = nodes[ index ];
						return 1;
					}
				}
				
				close[ index ] = 1;
			}
			
		}

		return 0;
	}

	
	void clear()
	{
		resultNode = null;
		
		if ( topNode != null )
		{
			topNode.clear();
			topNode = null;
		}
		
		openCount = 0;
		openResultCount = 0;

		for ( int i = 0 ; i < maxX * maxY ; i++ )
		{
			close[ i ] = 0;
		}
	}


	public int getX( int index )
	{
		return index % maxX;
	}
	public int getY( int index )
	{
		return index / maxX;
	}
	
	public int getIndex( int x , int y )
	{
		if ( x < 0 || y < 0 || x >= maxX || y >= maxY )
		{
			return GameDefine.INVALID_ID;
		}

		return y * maxX + x;
	}
	
	public int findPath( out int[] buffer , int sx , int sy , int ex , int ey )
	{
		if ( maxX == 0 || maxY == 0 )  
		{
			buffer = new int[ 0 ];
			return 0;
		}

		setStartEnd( sx , sy , ex , ey );
		findPath();

		if ( resultNode == null ) 
		{
			buffer = new int[ 0 ];
			return 0;
		}
		
		int count = 0;
		PathNode node = resultNode;
		
		int[] buffer1 = new int[ MAXBUFF ];

		while ( node != null )
		{
			buffer1[ count ] = getIndex( node.posX , node.posY );
			node = node.parent;
			count++;
			
			if ( MAXBUFF == count )
			{
				count -= 1;
				break;
			}
		}

		buffer = new int[ count ];

		for ( int i = 0 ; i < count ; i++ )
		{
			buffer[ i ] = buffer1[ count - i - 1 ];
		}
		
		return count;
	}





	public ArrayList PathCache = new ArrayList();
	
	public bool compressePath( int[] buffer )
	{
		PathCache.Clear();

		if ( buffer.Length < 2 )
		{
			return false;
		}

		SAMapGrid grid1 = new SAMapGrid();
		SAMapGrid grid2 = new SAMapGrid();
		
		int index1 = buffer[ 0 ];
		int index2 = buffer[ 1 ];


		grid1.posX = getX( index1 );
		grid1.posY = getY( index1 );
		grid2.posX = getX( index2 );
		grid2.posY = getY( index2 );
		
		int lastDirect = SAMapDirection.GetDirection( grid1 , grid2 );
		
		PathCache.Add( index1 );

		for ( int i = 2 ; i < buffer.Length ; i++ ) 
		{
			index1 = index2;

			grid1.posX = grid2.posX;
			grid1.posY = grid2.posY;
			
			index2 = buffer[ i ];
			grid2.posX = getX( index2 );
			grid2.posY = getY( index2 );
			
			int direct = SAMapDirection.GetDirection( grid1 , grid2 );
			
			if ( lastDirect == direct ) 
			{
				continue;
			}
			else 
			{
				PathCache.Add( index1 );
			}
			
			lastDirect = direct;
		}
		
		PathCache.Add( index2 );

		return true;
	}
	
	
	public bool uncompressePath( int[] buffer )
	{
		PathCache.Clear();

		SAMapGrid grid1 = new SAMapGrid();
		SAMapGrid grid2 = new SAMapGrid();

		if ( buffer.Length < 2 )
		{
			return false;
		}
		
		int index1 = buffer[ 0 ];
		grid1.posX = getX( index1 );
		grid1.posY = getY( index1 );

		for ( int i = 1 ; i < buffer.Length ; i++ )
		{
			int index2 = buffer[ i ];
			
			grid2.posX = getX( index2 );
			grid2.posY = getY( index2 );

			int direct = SAMapDirection.GetDirection( grid2 , grid1 );

			switch ( direct ) 
			{
			case (int)SAMapDirectionType.EAST:
				for ( int j = 0 ; j < grid2.posX - grid1.posX ; j++ ) 
				{
					int index = getIndex( grid1.posX + j , grid1.posY );
					PathCache.Add( index );
				}
				break;
			case (int)SAMapDirectionType.SOUTH:
				for ( int j = 0 ; j < grid2.posY - grid1.posY ; j++ ) 
				{
					int index = getIndex( grid1.posX , grid1.posY + j );
					PathCache.Add( index );
				}
				break;
			case (int)SAMapDirectionType.WEST:
				for ( int j = 0 ; j < grid1.posX - grid2.posX ; j++ ) 
				{
					int index = getIndex( grid1.posX - j , grid1.posY );
					PathCache.Add( index );
				}
				break;
			case (int)SAMapDirectionType.NORTH:
				for ( int j = 0 ; j < grid1.posY - grid2.posY ; j++ ) 
				{
					int index = getIndex( grid1.posX , grid1.posY - j );
					PathCache.Add( index );
				}                
				break;
			case (int)SAMapDirectionType.NORTHEAST:
				for ( int j = 0 ; j < grid2.posX - grid1.posX ; j++ ) 
				{
					int index = getIndex( grid1.posX + j , grid1.posY - j );
					PathCache.Add( index );
				}
				break;
			case (int)SAMapDirectionType.NORTHWEST:
				for ( int j = 0 ; j < grid1.posX - grid2.posX ; j++ ) 
				{
					int index = getIndex( grid1.posX - j , grid1.posY - j );
					PathCache.Add( index );
				}
				break;
			case (int)SAMapDirectionType.SOUTHEAST:
				for ( int j = 0 ; j < grid2.posX - grid1.posX ; j++ ) 
				{
					int index = getIndex( grid1.posX + j , grid1.posY + j );
					PathCache.Add( index );
				}
				break;
			case (int)SAMapDirectionType.SOUTHWEST:
				for ( int j = 0 ; j < grid1.posX - grid2.posX ; j++ ) 
				{
					int index = getIndex( grid1.posX - j , grid1.posY + j );
					PathCache.Add( index );
				}
				break;
			default:
				// error,
				return false;
			}

			grid1.posX = grid2.posX;
			grid1.posY = grid2.posY;
			index1 = index2;
		}
		
		PathCache.Add( index1 );

		return true;
	}


}

